package com.lyz.dataStructure.algorithm.搜狗2020;

import java.util.Scanner;

/**
 *@Author:759057893@qq.com Lyz
 *@Date: 2019/9/10 18:26
 *@Description:
 **/

/*
一个有序数组，找到比目标值大的第一个元素，如果比目标值大的第一个元素有重复数据，则找比目标值大的第二个元素
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
            String s =sc.nextLine();
            String[] st = s.split(" ");
            int[] arr = new int[st.length];
            for(int i =0;i<arr.length;i++){
                arr[i] = Integer.parseInt(st[i]);
            }
            int target = sc.nextInt();
            System.out.println(returnNum(arr,target));
    }
//1 3 5 8 9 9 10    8
    public static int returnNum(int[] arr, int target){
        if(arr.length==0||arr==null) return 0;
        int left = 0;
        int right = arr.length-1;
        while (left<right){
            int mid = (left+right)/2;
            if(arr[mid]==target){
                int count=1;
                for(int i =mid;i<=right-2;i++){
                    if(arr[i+1]==arr[i+2]){
                        count++;
                        return arr[count+mid+1];
                    }else {
                        return arr[mid+1];
                    }
                }
            }else if(arr[mid]>target){
                if(arr[mid-1]<=target){
                    return arr[mid];
                }
                right =mid-1;
            }else if(arr[mid]<target) {
                left = mid+1;
            }
        }
        return -1;
    }
}
